package xyz.noark.core.lang;

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

/**
 * 增强版四叉树，用于SLG游戏大地图单位管理
 */
public class QuadTree {

    private static final int CAPACITY = 4;
    private static final int MAX_LEVEL = 8;

    private final double x, y, width, height;
    private final int level;
    private final QuadTree parent;

    private final List<Unit> units;
    private QuadTree[] children;

    // 线程安全：使用读写锁
    private final ReadWriteLock lock = new ReentrantReadWriteLock();

    public static class Unit {
        public int id;
        public double x, y;

        public Unit(int id, double x, double y) {
            this.id = id;
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return String.format("Unit{id=%d, x=%.1f, y=%.1f}", id, x, y);
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Unit unit = (Unit) o;
            return id == unit.id;
        }

        @Override
        public int hashCode() {
            return Objects.hash(id);
        }
    }

    // 构造函数
    public QuadTree(double x, double y, double width, double height) {
        this(x, y, width, height, 0, null);
    }

    private QuadTree(double x, double y, double width, double height, int level, QuadTree parent) {
        this.x = x;
        this.y = y;
        this.width = width;
        this.height = height;
        this.level = level;
        this.parent = parent;
        this.units = new ArrayList<>();
        this.children = null;
    }

    private boolean contains(double px, double py) {
        return px >= x && px < x + width && py >= y && py < y + height;
    }

    private boolean inRect(double px, double py, double rx, double ry, double rw, double rh) {
        return px >= rx && px < rx + rw && py >= ry && py < ry + rh;
    }

    private boolean inCircle(double px, double py, double cx, double cy, double r) {
        double dx = px - cx, dy = py - cy;
        return dx * dx + dy * dy <= r * r;
    }

    private void split() {
        if (children != null) return;

        double hw = width / 2;
        double hh = height / 2;
        children = new QuadTree[4];

        children[0] = new QuadTree(x, y, hw, hh, level + 1, this);
        children[1] = new QuadTree(x + hw, y, hw, hh, level + 1, this);
        children[2] = new QuadTree(x, y + hh, hw, hh, level + 1, this);
        children[3] = new QuadTree(x + hw, y + hh, hw, hh, level + 1, this);
    }

    /**
     * 插入单位
     */
    public boolean insert(Unit unit) {
        lock.writeLock().lock();
        try {
            if (!contains(unit.x, unit.y)) return false;

            if (children == null && units.size() < CAPACITY && level < MAX_LEVEL) {
                units.add(unit);
                return true;
            }

            if (children == null) {
                split();
                // 重新分布现有单位
                List<Unit> temp = new ArrayList<>(units);
                units.clear();
                for (Unit u : temp) {
                    for (QuadTree child : children) {
                        if (child.insert(u)) break;
                    }
                }
            }

            for (QuadTree child : children) {
                if (child.insert(unit)) return true;
            }
            return false;
        } finally {
            lock.writeLock().unlock();
        }
    }

    /**
     * 批量插入
     */
    public void insertAll(List<Unit> units) {
        for (Unit u : units) {
            insert(u);
        }
    }

    /**
     * 删除单位（从当前节点或子节点）
     */
    public boolean remove(Unit unit) {
        lock.writeLock().lock();
        try {
            // 先检查是否在当前范围内
            if (!contains(unit.x, unit.y)) return false;

            // 尝试从当前节点删除
            if (units.remove(unit)) {
                // 删除后尝试合并（可选优化）
                tryMerge();
                return true;
            }

            // 尝试从子节点删除
            if (children != null) {
                for (QuadTree child : children) {
                    if (child.remove(unit)) {
                        // 删除后尝试合并子树
                        tryMerge();
                        return true;
                    }
                }
            }
            return false;
        } finally {
            lock.writeLock().unlock();
        }
    }

    /**
     * 尝试合并：如果子节点都为空，可以合并回父节点
     */
    private void tryMerge() {
        if (children == null) return;

        boolean allEmpty = true;
        for (QuadTree child : children) {
            if (child.units.size() > 0 || child.children != null) {
                allEmpty = false;
                break;
            }
        }

        if (allEmpty) {
            children = null; // 合并
        }
    }

    /**
     * 更新单位位置
     */
    public boolean update(Unit oldUnit, Unit newUnit) {
        if (remove(oldUnit)) {
            return insert(newUnit);
        }
        return false;
    }

    /**
     * 查询矩形范围
     */
    public List<Unit> queryRange(double rx, double ry, double rw, double rh) {
        lock.readLock().lock();
        try {
            List<Unit> result = new ArrayList<>();

            if (x >= rx + rw || x + width <= rx || y >= ry + rh || y + height <= ry) {
                return result;
            }

            for (Unit u : units) {
                if (inRect(u.x, u.y, rx, ry, rw, rh)) {
                    result.add(u);
                }
            }

            if (children != null) {
                for (QuadTree child : children) {
                    result.addAll(child.queryRange(rx, ry, rw, rh));
                }
            }

            return result;
        } finally {
            lock.readLock().unlock();
        }
    }

    /**
     * 查询圆形范围
     */
    public List<Unit> queryCircle(double cx, double cy, double radius) {
        lock.readLock().lock();
        try {
            List<Unit> result = new ArrayList<>();

            // 快速剔除
            double testX = Math.max(cx, Math.min(cx, x + width));
            double testY = Math.max(cy, Math.min(cy, y + height));
            double dx = testX - cx, dy = testY - cy;
            if (dx * dx + dy * dy > radius * radius) {
                return result;
            }

            for (Unit u : units) {
                if (inCircle(u.x, u.y, cx, cy, radius)) {
                    result.add(u);
                }
            }

            if (children != null) {
                for (QuadTree child : children) {
                    result.addAll(child.queryCircle(cx, cy, radius));
                }
            }

            return result;
        } finally {
            lock.readLock().unlock();
        }
    }

    /**
     * 生成 SVG 可视化（用于调试地图分布）
     */
    public void exportToSVG(String filename) throws IOException {
        int canvasSize = 800;
        StringBuilder svg = new StringBuilder();
        svg.append(String.format("<svg width=\"%d\" height=\"%d\" xmlns=\"http://www.w3.org/2000/svg\">\n", canvasSize, canvasSize));
        svg.append("<rect width=\"100%\" height=\"100%\" fill=\"white\" />\n");

        // 绘制四叉树网格
        drawNode(svg, canvasSize, 0);

        // 绘制单位
        Collection<Unit> allUnits = getAllUnits();
        for (Unit u : allUnits) {
            int screenX = (int) (u.x / width * canvasSize);
            int screenY = (int) (u.y / height * canvasSize);
            svg.append(String.format("<circle cx=\"%d\" cy=\"%d\" r=\"4\" fill=\"blue\" />\n", screenX, screenY));
            svg.append(String.format("<text x=\"%d\" y=\"%d\" font-size=\"10\" fill=\"black\">%d</text>\n", screenX + 6, screenY, u.id));
        }

        svg.append("</svg>\n");

        Files.write(Paths.get(filename), svg.toString().getBytes());
        System.out.println("✅ SVG 地图已保存到: " + filename);
    }

    private void drawNode(StringBuilder svg, int canvasSize, int depth) {
        if (depth > 5) return; // 控制深度

        int x1 = (int) (x / width * canvasSize);
        int y1 = (int) (y / height * canvasSize);
        int w = (int) (width * canvasSize / 1000.0);
        int h = (int) (height * canvasSize / 1000.0);

        svg.append(String.format("<rect x=\"%d\" y=\"%d\" width=\"%d\" height=\"%d\" " + "fill=\"none\" stroke=\"gray\" stroke-width=\"0.5\" />\n", x1, y1, w, h));

        if (children != null) {
            for (QuadTree child : children) {
                child.drawNode(svg, canvasSize, depth + 1);
            }
        }
    }

    /**
     * 获取所有单位（调试用）
     */
    private Collection<Unit> getAllUnits() {
        lock.readLock().lock();
        try {
            List<Unit> all = new ArrayList<>(units);
            if (children != null) {
                for (QuadTree child : children) {
                    all.addAll(child.getAllUnits());
                }
            }
            return all;
        } finally {
            lock.readLock().unlock();
        }
    }

    // ==================== 性能测试 ====================

    public static void performanceTest() {
        QuadTree world = new QuadTree(0, 0, 1000, 1000);
        Random rand = new Random();
        List<Unit> units = new ArrayList<>();

        int N = 50_000; // 5万单位
        System.out.println("🧪 开始性能测试：插入 " + N + " 个单位...");

        long start = System.nanoTime();
        for (int i = 0; i < N; i++) {
            Unit u = new Unit(i, rand.nextDouble() * 1000, rand.nextDouble() * 1000);
            units.add(u);
            world.insert(u);
        }
        long insertTime = System.nanoTime() - start;
        System.out.printf("✅ 插入耗时: %.2f ms\n", insertTime / 1_000_000.0);

        // 查询测试
        start = System.nanoTime();
        for (int i = 0; i < 1000; i++) {
            double cx = rand.nextDouble() * 1000;
            double cy = rand.nextDouble() * 1000;
            world.queryCircle(cx, cy, 50);
        }
        long queryTime = System.nanoTime() - start;
        System.out.printf("✅ 1000次范围查询耗时: %.2f ms (平均 %.2f ms/次)\n", queryTime / 1_000_000.0, (queryTime / 1_000_000.0) / 1000);

        // 更新测试
        start = System.nanoTime();
        for (int i = 0; i < 1000; i++) {
            Unit oldUnit = units.get(rand.nextInt(units.size()));
            Unit newUnit = new Unit(oldUnit.id, oldUnit.x + 10, oldUnit.y + 10);
            world.update(oldUnit, newUnit);
        }
        long updateTime = System.nanoTime() - start;
        System.out.printf("✅ 1000次移动更新耗时: %.2f ms\n", updateTime / 1_000_000.0);
    }

    // ==================== 主函数 ====================

    public static void main(String[] args) {
        QuadTree world = new QuadTree(0, 0, 1200, 1200);

        // 测试数据
        List<Unit> units = Arrays.asList(new Unit(1, 100, 100), new Unit(2, 150, 150), new Unit(3, 800, 800), new Unit(4, 200, 200), new Unit(5, 900, 900));

        world.insertAll(units);
        System.out.println("✅ 批量插入 " + units.size() + " 个单位");

        // 删除测试
        world.remove(units.get(0));
        System.out.println("✅ 删除 Unit{id=1}");

        // 更新测试
        Unit u2 = units.get(1);
        Unit u2New = new Unit(u2.id, 300, 300);
        world.update(u2, u2New);
        System.out.println("✅ 移动 Unit{id=2} 到 (300,300)");

        // 查询
        List<Unit> result = world.queryCircle(300, 300, 150);
        System.out.println("\n--- 范围查询结果 ---");
        result.forEach(System.out::println);

        // 生成可视化
        try {
            world.exportToSVG("quadtree_map.svg");
        } catch (IOException e) {
            e.printStackTrace();
        }

        // 性能测试
        System.out.println("\n" + "=".repeat(50));
        performanceTest();
    }
}